//file: MaxHeap.java
//This file is to define a max heap data structure

import java.util.*;
/*
 * <p> help </p>
 * @author Sam Jenkins
 */
public class MaxHeap
{
	private BTNode root;
	private int nodeCount;

	// Constructors
	public MaxHeap()
	{
		root = new BTNode(null, null, null, null);
		nodeCount = 0;
	}

	public MaxHeap(Object o)
	{
		root = new BTNode(o, null, null, null);
		nodeCount = 1;
	}


	// Return true if the heap is empty.
	// Otherwise, return false.
	public boolean isEmpty()
	{
		try{
			if ( root.getData() != null )
				return false;
			if ( root.getData() == null )
				return true;
			if ( root == null )
				return true;

		}
		catch(NullPointerException e){
			return true;
		}
		return false;
	}

	// Return number of nodes in the heap
	public int sizeOfHeap()
	{
		if(root == null || root.getData()== null)
			return 0;
		int i = 0;
		Iterator itr = this.heapItr();
		while(itr.hasNext() == true)
		{
			itr.next();
			i++;
		}
		return i;
	}

	// return the height of the heap.
	public int heightOfHeap()
	{
		if(this.isEmpty())
			return 0;

		int height = 0;
		BTNode cursor = root;
		while(cursor.getLeft() != null)
		{
			cursor = cursor.getLeft();
			height++;
		}
		return height;			
	}


	// return true if the tree is full.
	// otherwise return false.
	public boolean isFull()
	{
		if(this.isEmpty())
			return true;
		// if left flank equals right flank then true else false
		int leftSide = this.heightOfHeap();
		int rightSide = 0;

		BTNode temp = root;
		while(temp.getRight() != null)
		{
			rightSide++;
			temp = temp.getRight();
		}
		return (leftSide == rightSide);
	}

	// Return the first node having a null child in the heap. That is,
	// the first node has a null child in the level order sequence.
	// This method is called to located the correct position for insertion.
	// If the heap is an empty heap, then return null.
	public BTNode firstNodeWithNullChild()
	{
		//if(this.isEmpty())
		//	return null;
		Iterator itr = this.heapItr();
		BTNode cursor = (BTNode)itr.next();

		while( cursor.getLeft() != null && cursor.getRight() != null )
			cursor = (BTNode)itr.next();// advance the cursor until a node is found without a child
		return cursor;
	}

	// Return the last node in the heap in the level order sequence.
	// This method is called to locate the node to be physically
	// deleted from the heap for removal.
	// If the heap is empty, return null.
	public BTNode lastNode()
	{
		// use iterator to cycle through all of the nodes
		//
		if(this.isEmpty())
			return null; // or throw NullPointerException
		Iterator itr = this.heapItr();
		BTNode cursor = null;
		while(itr.hasNext())
			cursor = (BTNode)itr.next();

		return cursor;
	}

	// PRE: both node's left subtree and right subtree are heaps
	// POST: push down the  'node' to its correct position
	//       and make the tree a heap.
	public void maxHeapifyDown(BTNode node)
	{
		BTNode cursor = node; // use cursor to cycle down through the tree
		while( cursor.getRight() != null )
			if(((Process)cursor.getRight().getData()).compareTo(((Process)cursor.getLeft().getData())) == 1)
			{
				if (((Process)cursor.getRight().getData()).compareTo((Process)cursor.getData()) == 1)
				{
					this.swap(cursor, cursor.getRight());
					cursor = cursor.getRight();
				}else
					break;
			}else{
				if (((Process)cursor.getLeft().getData()).compareTo((Process)cursor.getData()) == 1)
				{
					this.swap(cursor, cursor.getLeft());
					cursor = cursor.getLeft();
				}else
					break;
			}
		if ( cursor.getLeft() != null )
			if (((Process)cursor.getLeft().getData()).compareTo((Process)cursor.getData()) == 1)
			{
				this.swap(cursor,cursor.getLeft());
			}			
	} // closes maxHeapifyDown method


	// PRE:  each node has data to be swapped (not null)
	// POST: swap data from each node to the other node
	// 
	private void swap(BTNode node1, BTNode node2)
	{
		Object tempObj = node1.getData();
		// set data from node2 to node1
		node1.setData(node2.getData());
		// set data from node1 to node2
		node2.setData(tempObj);
	}


	// PRE: All other nodes, except the node, are in their correct 
	//      positions as a heap.
	// POST: bubble up the node to its correct position
	//       and make the tree a heap.
	public void maxHeapifyUp(BTNode node)
	{
		// assign node to cursor Node that will travel up the heap
		BTNode cursor = node;

		// compare node with it's parent and swap if node is larger than parent
		// continue until node is either smaller than it's parent or you have reached the root.

		// compare node to parent...  if parent is smaller... swap   if temp == root then stop
		while (cursor != root && ((int)(((Process)cursor.getData()).compareTo((Process)cursor.getParent().getData()))) == 1)
		{
			// set parent data to a temp Node and copy data from child to parent
			// then copy data from temp to child
			swap(cursor,cursor.getParent());
			// set node to it's parent
			cursor = cursor.getParent();
		}
	}



	// PRE: the tree pointed by root is not necessarily a heap
	// POST: make the tree a heap
	public void buildHeap()
	{
		//heapify down on all nodes
		
		Iterator itr = this.heapItr();
		while(itr.hasNext())
			this.maxHeapifyDown((BTNode)itr.next());		
	}
	

	// PRE: insert a new node contaning the object o into the heap
	// POST: the new object is inserted. 
	public void insert(Object o)
	{

		if(this.isEmpty())
		{
			root.setData(o);
			//System.out.println(o.toString() + " root");
			return;
		}

		BTNode last = firstNodeWithNullChild();
		BTNode newChild = new BTNode(o,null,null,last);
		if(last.getLeft() == null)
		{
			last.setLeft(newChild);
			//System.out.println(o.toString() + " left");
			this.maxHeapifyUp(newChild);
		}else{
			last.setRight(newChild);
			//System.out.println(o.toString() + " right");
			this.maxHeapifyUp(newChild);
		}
		
	}


	// PRE: remove the object in the root node from the heap.
	//      if the heap is empty, throw NoSuchElementException.
	// POST: the object in the root is removed and returned.
	public Object remove()
	{
		if(this.isEmpty())
			throw new NoSuchElementException("The MaxHeap is empty");
		Object objRemoved = root.getData();
		BTNode lastNode = this.lastNode();
		if(root == lastNode)
		{
			root.setData(null);
			return objRemoved;
		}
		root.setData(lastNode.getData());

		// find out whether the last node is the left or right child of it's parent 
		// and set that parents link to null, thus deleting that node.
		if(lastNode.getParent().getRight() == lastNode)
			lastNode.getParent().setRight(null);
		else
			lastNode.getParent().setLeft(null);

		maxHeapifyDown(root);		

		return objRemoved;
	}


	// public method to return a heap iterator
	public Iterator heapItr()
	{
		return new heapIterator();
	}


	// inner class to implement the Iterator interface
	// return the nodes of the heap in a level order traversal
	private class heapIterator implements Iterator
	{
		private  LinkedListQueue q;

		// Constructor
		public heapIterator()
		{
			q = new LinkedListQueue();
			if (root != null)
				q.enQueue(root);
		}

		// return true if there are more nodes in the heap.
		// otherwise, return false.
		public boolean hasNext()
		{
			if(q.isEmpty())
				return false;
			return true;
		}

		// PRE: hasNext() return true.
		// POST: return the next node in the heap.
		public Object next()
		{
			// dequeue and enqueue it's children
			// return Object

			BTNode parent = null, leftChild, rightChild;
			if(this.hasNext())
			{
				parent = ((BTNode)q.getFront());
				leftChild = parent.getLeft();
				rightChild = parent.getRight();
				if(leftChild != null)		// if there is a left child
					q.enQueue(leftChild);	// put in LinkedListQueue
				if(rightChild != null)		// if there is a right child
					q.enQueue(rightChild);	// put in LinkedList Queue
				return q.deQueue();			// return node in the front of LinkedListQueue
			}
			// throw Exception
			return parent.getData();

		}

		// Do nothing for this method
		public void remove(){}
	}	
}